﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace QuickShort
{
    class Program
    {
        static void Main(string[] args)
        {

            #region 生成随机数列

            int count = 10000;
            List<int> bufferList = new List<int>();
            for (int i = 0; i < count; i++)
            {
                int v = new Random().Next(0, 100000);
                while (bufferList.Contains(v))
                    v = new Random().Next(0, 100000);
                bufferList.Add(v);
            }

            int[] buffer = bufferList.ToArray();

            #endregion

            Stopwatch stopWatch = new Stopwatch();
            int start = 0;
            int end = buffer.Length - 1;
            stopWatch.Start();
            QuickShort(buffer, start, start, end);
            var ts = stopWatch.Elapsed.TotalMilliseconds;
            stopWatch.Stop();
            foreach (var item in buffer)
                Console.WriteLine($"{item}");

            Console.WriteLine($"耗时：{ts.ToString("F5")} ms");

        }


        //快速排序
        private static void QuickShort(int[] buffer, int currentIndex, int start, int end)
        {
            if (start == end)
                return;

            for (int i = start; i <= end; i++)
            {
                if (buffer[currentIndex] > buffer[i])
                {
                    for (int j = i - 1; j >= currentIndex; j--)
                    {
                        Swap(buffer, j + 1, j);
                    }
                    currentIndex++;
                }
            }
            if (currentIndex > start)
            {
                int newEnd = currentIndex - 1;
                QuickShort(buffer, start, start, newEnd);
            }

            if (currentIndex < end)
            {
                int newStart = currentIndex + 1;
                QuickShort(buffer, newStart, newStart, end);
            }

        }

        ///交换两个变量位置
        private static void Swap(int[] buffer, int source, int dest)
        {
            buffer[source] = buffer[source] + buffer[dest];
            buffer[dest] = buffer[source] - buffer[dest];
            buffer[source] = buffer[source] - buffer[dest];
        }
    }
}
